#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstring>
#include <functional>
#include <numeric>
#include <vector>

using namespace std;

enum {
  LEFT,
  RIGHT,
};

using PermutationCallback = function<void(vector<int> &)>;

void PrintPermutation(vector<int> &a) {
  for (auto val : a) {
    printf(" %d", val);
  }
  puts("");
}

// Mobile number: a number whose arrow points to a smaller number.
// Return the index of the maximum mobile number or -1 if no MN can be found.
int FindMaxMobileNumber(vector<int> &a, vector<int> &tag) {
  int max_val = INT_MIN;
  int ans = -1;
  int N = a.size();
  for (int i = 0; i < N; ++i) {
    int t = tag[i];
    if ((t == LEFT && i > 0 && a[i] > a[i - 1]) ||
        (t == RIGHT && i < N - 1 && a[i] > a[i + 1])) {
      if (a[i] > max_val) {
        max_val = a[i];
        ans = i;
      }
    }
  }
  return ans;
}

// Generate all the permutations started from `a` using SJT algorithm.
// For each permutation (including the initial input one), the `callback` will
// be fired. After that, the total number of permutations will be printed.
void SJT_Permutation(vector<int> &a, PermutationCallback callback) {
  // The tag array records the direction of each number (LEFT or RIGHT).
  // When a number moves, its value (in `a`) and direction (in `tag`) should
  // move together as one entity.
  vector<int> tag;
  tag.resize(a.size());
  fill(tag.begin(), tag.end(), LEFT);
  // For the initial one.
  callback(a);
  int total = 1;

  int pos; // The index of the MMN (Max Mobile Number).
  while ((pos = FindMaxMobileNumber(a, tag)) != -1) {
    int t = tag[pos];
    int val = a[pos];

    // Move the MMN according to its direction.
    if (t == LEFT) {
      // Note: the number moves with its direction changed.
      swap(a[pos - 1], a[pos]);
      swap(tag[pos - 1], tag[pos]);
    } else { // right
      swap(a[pos + 1], a[pos]);
      swap(tag[pos + 1], tag[pos]);
    }
    // A new permutation was generated.
    callback(a);
    ++total;
    // For any number larger than the moved one, flip its direction.
    for (int i = 0; i < a.size(); ++i) {
      if (a[i] > val) {
        tag[i] = !tag[i];
      }
    }
  }
  printf("total: %d\n", total);
}

// From back to front, find the first number that is smaller than its successor.
// That is, the first number that descends in value. If all the numbers are
// ascending, this means the last permutation (in reversed natural order) is
// reached so the algorithm should terminate.
int FindFirstDescending(vector<int> &a) {
  for (int i = a.size() - 1; i > 0; --i) {
    if (a[i - 1] < a[i]) {
      return i - 1;
    }
  }
  return -1;
}

// Find the smallest number that is larger than the First-Descending-Number in
// the range (FDN, last-one]. This number will be swapped with the FDN.
int FindSmallestLarger(vector<int> &a, int pos) {
  int min_val = INT_MAX;
  int ans = -1;

  for (int i = pos + 1; i < a.size(); ++i) {
    if (a[i] > a[pos] && a[i] < min_val) {
      min_val = a[i];
      ans = i;
    }
  }
  assert(ans != -1);
  return ans;
}

// Generate permutations in dictionary order. This is also the algorithm adopted
// by STL.
void DictionaryOrder_Permutation(vector<int> &a, PermutationCallback callback) {
  int N = a.size();
  int total = 1;
  callback(a);
  int pos;
  while ((pos = FindFirstDescending(a)) != -1) {
    int j = FindSmallestLarger(a, pos);
    swap(a[pos], a[j]);
    // Reverse the range (FND, last-one].
    reverse(a.begin() + pos + 1, a.end());
    callback(a);
    ++total;
  }
  printf("total: %d\n", total);
}

// Create an initial permutation of size `N` (in natural order).
vector<int> InitPermutation(int N) {
  vector<int> a;
  a.resize(N);
  iota(a.begin(), a.end(), 1);
  return a;
}

int main(int argc, char **argv) {
  while (1) {
    int N;
    scanf("%d", &N);
    auto a = InitPermutation(N);
    // SJT_Permutation(a, PrintPermutation);
    DictionaryOrder_Permutation(a, PrintPermutation);
  }

  return 0;
}
